#include <iostream>
#include <string>
#include <vector>
using namespace std;

template<class K, class V>
struct HashNode
{
  HashNode(const pair<K, V>& data)
    :_kv(data)
    ,_next(nullptr)
  {}

  pair<K, V> _kv;
  struct HashNode* _next;
};

template<class K>
struct HashKey 
{
  size_t operator()(const K& key)
  {
    return key;
  }
};

template<>
struct HashKey<string>
{
  size_t operator()(const string& s)
  {
    size_t ret = 0;
    for(const auto e : s)
    {
      ret = ret * 131 + e;
    }
    return ret;
  }
};

template<class K, class V, class GetHashKey = HashKey<K>>
class HashTable
{
    typedef struct HashNode<K, V> HashNode;
  public:
    // 通过key查找哈希表中的数据
    HashNode* Find(const K& key)
    {
      // 有效数据为0的话直接退出
      if(_n == 0)
        return nullptr;
      // 1、通过除留余数法计算key的地址
      GetHashKey kot;
      size_t index = kot(key) % _table.size();
      // 2、遍历单链表中所有节点的key，看是否有对应的
      if(_table[index])
      {
        HashNode* cur = _table[index];
        while(cur)
        {
          if(cur->_kv.first == key)
          {
            return cur;
          }
          else 
          {
            cur = cur->_next;
          }
        }
      }
      // 遍历完单链表也没有找到说明不存在，返回空即可
      return nullptr;
    }

    bool Insert(const pair<K, V>& data)
    {
      if(Find(data.first))
        return false;

      GetHashKey kot;
      if(_n == _table.size())
      {
        size_t length = _table.size()==0 ? 10 : 2 * _table.size();
        vector<HashNode*> newTable(length, nullptr);
        for(size_t i = 0; i < _table.size(); ++i)
        {
          if(_table[i])
          {
            HashNode* cur = _table[i];
            while(cur)
            {
              HashNode* next = cur->_next;
              size_t index = kot(data.first) % length;
              cur->_next = newTable[index];
              newTable[index] = cur;
              cur = next; 
            }
            _table[i] = nullptr;
          }
        }
        _table.swap(newTable);
      }
      size_t index = kot(data.first) % _table.size();
      HashNode* newNode = new HashNode(data);
      newNode->_next = _table[index];
      _table[index] = newNode;
      ++_n;
      return true;
    }

    bool Erase(const K& key)
    {
      // 有效数据个数为0时直接退出，删除失败 
      if(_n == 0)
        return false;

      // 1、通过除留取余法找到key值对应的桶的位置
      GetHashKey kot;
      size_t index = kot(key) % _table.szie();
      // 2、记录好前一个节点prev，从第一个节点cur开始往后找要删除的节点。
      HashNode* prev = nullptr;
      HashNode* cur = _table[index];
      while(cur)
      {
        if(cur->_kv.first == key)
        {
          if(prev == nullptr)
          {
            _table[index] = cur->_next;
          }
          else 
          {
            prev->_next = cur->_next;
          }
          delete cur;
          --_n;
          return true;
        }
        else 
        {
          cur = cur->_next;
        }
      }
      // 遍历完单链表后依然没有找到说明不存在该节点，删除失败
      return false;
    }

    void PrintHashTable()
    {
      for(size_t index = 0; index < _table.size(); ++index)
      {
        if(_table[index])
        {
          HashNode* cur = _table[index];
          while(cur)
          {
            cout<<'<'<<cur->_kv.first<<", "<<cur->_kv.second<<'>'<<endl;
            cur = cur->_next;
          }
        }
      }
    }

  private:
    size_t _n = 0;
    vector<HashNode*> _table;
};
